//四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> ret;
        int n = nums.size();

        //1、排序
        sort(nums.begin(),nums.end());

        //依旧是利用三数之和的思想来解决
        for(int i = 0; i < n;)//固定一个数a
        {
            for(int j = i + 1;j < n;)//固定一个数b
            {
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i]-nums[j];
                while(left < right)
                {
                    long long sum = nums[right] + nums[left];
                    if(aim > sum)
                        left++;
                    else if(aim < sum)
                        right--;
                    else 
                    {
                        ret.push_back({nums[left],nums[right],nums[i],nums[j]});
                        left++;
                        right--;

                        //去重left 和 right
                        while(left < right && nums[left] == nums[left-1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;

                    }
                }
                //去重j
                j++;
                while(j < n && nums[j] == nums[j-1]) j++;
            }
            //去重i
            i++;
            while(i < n && nums[i] == nums[i-1]) i++;
        }
        return ret;

    }
};

//无重复字符的最长子串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        //解题思路：根据规律运用滑动窗口
        //现创建一个hash数组
        int hash[128] = {0};
        int n = s.size(), ret = 1;
        for(int left = 0, right = 0; right < n; right++)
        {
            //进窗口
            hash[s[right]]++;
            //判断
            while(hash[s[right]] > 1)
            {
                //出窗口
                hash[s[left++]]--;
            }
            ret = max(ret,right-left+1);//更新结果
            
        }
        return n == 0 ? 0 : ret;
    }
};

//最大连续1的个数|||
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int n = nums.size();
        int ret = 0; //用于保存结果
        int hash[2] = {0}; // 模拟hash，用来统计0的个数

        //利用滑动窗口来解决问题
        for(int left = 0, right = 0; right < n; right++)
        {
            //进窗口
            hash[nums[right]]++;
            while(hash[0] > k)//判断
            {
                //出窗口
                hash[nums[left++]]--;
            }
            //更新结果
            ret = max(ret, right - left + 1);
        } 
        return ret;
    }
};

//  将x减到0的最小操作数
class Solution {
public:
    int minOperations(vector<int>& nums, int x) 
    {
        //使用正难则反的思路，将问题转化成求区间内和为total-x的最长长度
        int n = nums.size();
        int total = 0; // 计算数组的总和
        int ret = -1; //返回值
        for(auto e : nums) total += e;
        int target = total - x;


        if(target < 0) //判断特殊情况
            return -1;

        for(int left = 0, right = 0, sum = 0; right < n; right++)
        {   
            //进窗口
            sum += nums[right];
            while(sum > target) //判断
                sum -= nums[left++]; //出窗口
            
            if(sum == target) 
            {
                ret = max(ret, right - left + 1);
            }
        }
        if(ret == -1) 
            return -1;
        else 
            return n - ret;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    bool check(TreeNode* p, TreeNode* q)
    {
        if(!q && !p) return true;
        if(!q || !p) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) 
    {
        return check(root, root);
    }
};

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        dfs(A, B, C, A.size());
    }

    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {
        //递归出口
        if(n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        dfs(A, C, B, n - 1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B, A, C, n - 1);
    }

};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        //当便利到第一个叶子结点或者head为空就直接返回
        if(head == nullptr || head->next == nullptr)
            return head;
        
        ListNode* newHead= reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

class Solution {
public:
    double myPow(double x, long long n)
    {
        if(n == 0)
            return 1.0;
        if(n < 0)
            return 1.0 / myPow(x, -n);

        double tmp = myPow(x, n / 2);
        return n % 2 == 0 ? tmp*tmp : tmp*tmp*x;
    }
};